package edu.cmu.cs211.bacon.util;

import java.util.ArrayList;

/**
 * An implementation of the UnionFind algorithm
 */
public class UnionFind<T> {

	T p[];
	int rank[];
	ArrayList<T> list;

	@SuppressWarnings("unchecked")
	//the element that is not in any union should have parent of null
	public UnionFind(ArrayList<T> list) {
		if(list == null)
			throw new NullPointerException();
		this.list = list;
		int n = list.size();
		p = (T[])new Object[n]; 
		rank = new int[n];
		for(int i=0;i<n; i++){
			p[i] = null;
			rank[i] = 0;
		}
	}

	/**
	 * Unions the sets containing elements a and b together. If a and b
	 * are already in the same set, this method will do nothing.
	 *
	 * @throws NullPointerException if a or b is null
	 */
	public void union(T a, T b) {
		if(a == null || b == null)
			throw new NullPointerException();
		//let the parent of b be the head of the union
		int h1 = list.indexOf(find(a));
		int h2 = list.indexOf(find(b));
		if(rank[h1]>rank[h2]){
			p[h2] = a;
			return;
		}
		p[h1] = b;
		if(rank[h1]==rank[h2]) rank[h2]++;
	}

	/**
	 * Returns the canonical element representing the set a is in.
	 * 
	 * @param a		the element to be queried
	 * @return		the canonical element representing the set a is in
	 * @throws		NullPointerException if a is null
	 */
	public T find(T a) {
		int x = list.indexOf(a);
		if (p[x] == null) 
			return a; 
		else{
			return (p[x] = find(p[x]));
		}
	}

	/**
	 * Resets this Union-Find so that each element is its own canonical element (ie.
	 * each element is in its own set).
	 */
	@SuppressWarnings("unchecked")
	//set all to null 
	public void clear() {
		int n = list.size();
		p = (T[])new Object[n]; 
		rank = new int[n];
		for(int i=0;i<n; i++){
			p[i] = null;
			rank[i] = 0;
		}
	}
}
